#include "lru.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Page
{
  char data;
  int stay;
};

/**
 * 函数：模拟LRU页面置换算法。
 *
 * @param queue_frames 一个字符串，表示页面访问序列。
 *                     字符串中的每个字符是一个数字，表示一个页面号。
 * @param num_frames   页框的数量，表示物理内存中可用的页框数。
 */
void
lru_page_replacement (char *queue_frames, int num)
{
  // TODO
  // 使用数组记录页表项
  struct Page pages[10];
  // 记录当前内存中的页面数量
  int count = 0;
  for (int i = 0; queue_frames[i] != '\0'; i++)
  {
    // 如果遇到','字符，跳过
    if (queue_frames[i] == ',') continue;
    printf ("Access:%c,", queue_frames[i]);
    int is_exist = 0;
    int page_idx = 0;
    // 判断该页面是否已在内存中
    for (int k = 0; k < count; k++)
    {
      if (pages[k].data == queue_frames[i])
      {
        is_exist = 1;
        page_idx = k;
        break;
      }
    }
    // 不存在，则判断是否需要页面置换
    if (!is_exist)
    {
      // 如果页表未满，添加页面到页表
      if (count < num)
      {
        pages[count].data = queue_frames[i];
        pages[count].stay = 0;
        
        count++;
      }
      // 页表已满，置换stay值最大即驻留时间最长的页面
      else
      {
        int max_idx = 0;
        for (int k = 0; k < num; k++)
        {
          if (pages[k].stay > pages[max_idx].stay)
            max_idx = k;
        }
        pages[max_idx].data = queue_frames[i];
        pages[max_idx].stay = 0;
      }
    }
    else
    {
      pages[page_idx].stay = 0;
    }

    // 页面stay值统一+1
    for (int k = 0; k < count; k++)
    {
      pages[k].stay++;
    }
    // 打印页表项
    printf ("Frames: [");
    int cnt = 0;
    for (int k = 0; k < count; k++)
    {
      cnt++;
      printf ("%c", pages[k].data);
      if (cnt != count) printf (",");
    }
    if (cnt < num)
    {
      int pad_num = num - cnt;
      while (pad_num--)
      {
        printf (",-1");
      }
    }
    printf ("]\n");
  }
}
